ডিগ্রি (Degree)
ডিগ্রি হলো একটি নোড বা ভের্টেক্সের সাথে সংযুক্ত এজের সংখ্যা। গ্রাফের প্রতিটি নোডের একটি নির্দিষ্ট ডিগ্রি থাকে, যা সেই নোডে পৌঁছানো বা সেই নোড থেকে সংযোগিত এজের সংখ্যা নির্দেশ করে।
- ইন-ডিগ্রি (In-degree): একটি ডাইরেক্টেড গ্রাফে কোনো নোডে আসা এজের সংখ্যা।
- আউট-ডিগ্রি (Out-degree): একটি ডাইরেক্টেড গ্রাফে কোনো নোড থেকে বের হওয়া এজের সংখ্যা।
উদাহরণ: যদি একটি নোড \( A \) এর সাথে তিনটি এজ যুক্ত থাকে, তবে \( A \)-এর ডিগ্রি হবে ৩।
পথ (Path)
পথ হলো নোডগুলোর একটি সিকোয়েন্স যা এজের মাধ্যমে সংযুক্ত থাকে। একটি নির্দিষ্ট নোড থেকে শুরু করে অন্য একটি নোডে পৌঁছানোর জন্য যে নোড ও এজের সিকোয়েন্স ফলো করা হয়, তাকে পথ বলা হয়।
- পথের দৈর্ঘ্য: এটি সেই পথের এজের সংখ্যা নির্দেশ করে।
- সাধারণ পথ (Simple Path): এমন একটি পথ যেখানে কোনো নোডের পুনরাবৃত্তি হয় না।
উদাহরণ: গ্রাফ \( G \)-এর নোডগুলি \( A \to B \to C \) এ সংযুক্ত হলে, এটি \( A \)-থেকে \( C \)-এ যাওয়ার একটি পথ নির্দেশ করে।
সার্কিট (Circuit)
সার্কিট হলো এমন একটি বন্ধ পথ যেখানে শুরু এবং শেষের নোড একই, এবং একবারের বেশি কোনো এজ বা নোড ব্যবহার করা হয় না। সার্কিটগুলি গ্রাফে পুনরাবৃত্তি ছাড়া একটি সিকোয়েন্সের মাধ্যমে নোডে সংযোগ স্থাপন করে।
- সার্কিটের বৈশিষ্ট্য: সার্কিটে প্রত্যেক নোড এবং এজ একবারই ব্যবহার করা হয়, তবে পথটি আবার প্রথম নোডে ফিরে আসে।
উদাহরণ: \( A \to B \to C \to A \) একটি সার্কিট।
সাইকেল (Cycle)
সাইকেল হল একটি বিশেষ ধরনের সার্কিট, যেখানে নোডগুলির মধ্যে পুনরাবৃত্তি হয় না, তবে শেষ নোড প্রথম নোডে ফিরে আসে। এটি এমন একটি বন্ধ পথ যা আবার সেই নোডেই শেষ হয়, যেখান থেকে শুরু হয়েছিল।
- সাধারণ সাইকেল (Simple Cycle): এমন একটি সাইকেল যেখানে প্রতিটি নোড একবারই দেখা হয়।
- অবহেলনীয় সাইকেল (Hamiltonian Cycle): এমন একটি সাইকেল যা গ্রাফের প্রতিটি নোডকে একবারই অন্তর্ভুক্ত করে।
উদাহরণ: যদি \( A \to B \to C \to D \to A \) হয় এবং এই পথে কোনো নোড পুনরাবৃত্তি না হয়, তবে এটি একটি সাইকেল।
সংক্ষেপে (Summary)
- ডিগ্রি: নোডের সাথে সংযুক্ত এজের সংখ্যা।
- পথ: দুটি নোডের মধ্যে সংযোগের জন্য ব্যবহৃত সিকোয়েন্স।
- সার্কিট: বন্ধ পথ যেখানে প্রথম এবং শেষ নোড একই।
- সাইকেল: পুনরাবৃত্তি ছাড়া বন্ধ পথ যা প্রথম নোডে ফিরে আসে।
Read more
